Software programming languages have evolved over time. In early machine code languages, computer instructions were written as numbers (machine language) or as human-readable versions of machine language (assembly language). Subsequent programming languages, such as Fortran and COBOL, introduced a measure of abstraction, so that a programmer wrote instructions in a higher-level source language, and a compiler or interpreter was needed to convert the language from the source language to machine language. More recently, further advances in programming languages have paved the way for quicker, more result-oriented programming techniques. However, an evolution in programming languages usually comes with a set of trade-offs. Advances in programming languages usually shorten the development cycle, but add processing and storage overhead to the program. Language developers strive to balance these trade-offs.
Many programming language trade-offs are reflected in how a compiler compiles source code. Generally speaking, a compiler is a piece of software that converts a program from a source programming language (which is readable, more easily understandable by humans) to machine language (sometimes called binary or object code, which the computer executes). The compiler analyzes the source code and, to produce more efficient code, performs program transformations, such as branch elimination, partial evaluation, or peep-hole optimization, on the code. For example, a computer programmer often writes source code that sets forth a logical flow of operations that is simple and intuitive for a human to follow, but is inefficient for a computer to execute. The compiler recognizes inefficiencies and improves the performance of the software at the machine code level by eliminating operations that are unnecessary to achieve the intended results. In this way, the programmer creates a robust software program that is useful and efficient in a reasonable period of time.
I. Object-oriented Programming
Object-oriented programming (“OOP”) over the last few years has become common for software development in many areas. OOP is often done in a programming language such as Java, C++, Python, or C#. Numerous models for OOP have been developed, and terminology varies from model to model.
In one abstract model, OOP is a software design method that models the characteristics of abstract or real objects using “classes” and “objects.” A class defines a template or prototype for an object. The structure and behavior of a class is determined by class variables (sometimes called properties or attributes) and methods (one term for software routines). An object is an instance of a class. An object is created when a variable of a class type is declared in a program. The object is produced by allocating a data structure that includes or references the variables and methods defined by the class template and by initializing the variables with either default values or those provided by a class constructor method.
Access to the data of an object is defined through methods which hide the internal workings of the object. This allows a programmer to develop a well-defined set of methods to manipulate variables and data. This also facilitates robust and secure programming because variable and data manipulation happen through the methods of an interface or an object's own internal methods.
II. Recursion
Recursion is a programming technique in which a software routine calls itself. When a method, function, or other routine calls itself, it is termed a recursive call. Recursion provides an intuitive way to model and solve many software problems, but can result in inefficiencies during execution. The classic example of recursive routine is a function for calculating factorials. A simple recursive function to calculate the factorial of a number is as follows:
int factorial(int n) {  if n = 0    return 1;  else    return n * factorial (n−1);}
Code Fragment 1
Usually, a recursive routine performs a test on its arguments to check for a “base case,” which is a condition under which the routine returns a value without calling itself, thus terminating the chain of recursive calls. In the factorial example, the function factorial checks to see if the base case (i.e., the number n being equal to zero) has been reached. If the base case has not been reached, the function calls itself, subtracting one from n to pass as the parameter. This process is repeated until the base case is reached. Then, the value 1 is returned to the preceding function call, which multiplies the returned value (1) by the value of n at that level in the recursive chain, then returns that product to the preceding function call, etc. This backing out process continues until the factorial function has exited all the preceding function calls, ultimately returning the result n*(n−1)*(n−2) . . . * 1 to the original caller.
During a recursive call, a complete new copy of the function's “information” (such as parameters, return addresses, etc.) is placed into memory, for example, as a stack frame on a stack for function calls. When a particular function call returns or exits, information for that function call is freed, effectively removing it from memory. Many levels of function calls can be initiated when performing recursion, resulting in numerous copies of information for the function call actively residing in memory. The function call factorial(100) results in 101 recursive function calls, for example. The function factorial is simple, but more complex functions include more operations in the body of the function call and result in an increased use of processing resources. Recursive routines, especially complex or lengthy ones, use a lot of computing resources compared to alternative, non-recursive implementations. However, recursive code will often be more compact, easier to design, develop, implement, integrate, test, and debug. This is especially true for recursive code for traversing complex data structures such as different types of tree data structures.
A variation on recursive calls is called tail-recursion. A call is tail-recursive if nothing has to be done in the function (except return) after the recursive call returns. A simple tail recursive function is as follows:
int tail_fac(int n, int m) {  if n = 0    return m;  else    return tail_fac(n−1, n*m);}
Code Fragment 2
The function in code fragment 2 is a tail-call recursive function because the last call made in the function is to itself, and when the call returns no other processing occurs. On the other hand, the function in code fragment 1 is not a tail-recursive function because it requires additional processing after a recursive call returns. Namely, when a recursive call returns, the returned value still needs to be multiplied by the value of n.
Tail-call recursive functions provide an opportunity for optimizing recursive functions; for example, when using tail-calls, it is not necessary to retain stack frames for the chained calls as the calling environment. This means that the function uses a constant amount of memory; only one copy of the function's information is ever residing in memory at one time. A simple way of translating the function of code fragment 2 for tail-call optimization (by a compiler or other tool) is as follows:
int tail_fac(int n, int m) {  start: if n = 0    return m;  else {    m = n*m;    n = n−1;    goto start;  }}
Code Fragment 3
Code fragment 3 illustrates an optimized version of the tail_fac function; it returns the same result as code fragment 2. However, in this example, the recursive call has been removed and a “goto” label has been added instead. The comparison (n=0) and goto statement essentially tell the function to keep looping until n is 0. Only one copy of the function is necessary at any one time because with each loop through the function the values are updated and carried forward to the next loop of the function.
In the following sections, the examples are somewhat simplified for the sake of illustration. Many of the recursive code fragments presented could be written in a non-recursive fashion. But the same principles apply in other scenarios where writing non-recursive code is either very difficult or just not possible. For example, writing code that will perform a depth-first traversal on a data structure such as a binary tree is easy to do using recursion, but is very difficult to do using non-recursive means. More generally, recursion often allows simple solutions to processing problems that involve complex, nested list structures. The problem might be solving a mathematical expression with an arbitrary number of nested sub-expressions (e.g., (w*(((x+3)*y)−z)), searching through a tree structure that explores the potential moves in a game, evaluating an arbitrarily complex statement following some grammar in a compiler, or some other problem requiring traversal of a complex, nested structure.
III. Iterators and Generators
Most programming languages, including database languages and document processing languages, support base types for collections of base elements (e.g., arrays of integers, strings of characters) as well as user-defined types for arbitrary collections of elements (e.g., enumerations of ordered elements) and more complex data structures such as trees, stacks, queues, and linked lists.
A software object for representing a collection of elements often provides methods for services such as insertion, deletion, searching, sorting, or testing an item for membership. Iterators encapsulate the logic for “walking over” or enumerating the elements of collections. An iterator accesses elements from a list, array, or other collection one at a time. By extension, an iterator can be used to access elements from another data structure (e.g., tree-shaped structure) that can be viewed as a list. In the programming language C#, for example, an iterator is a language construct that simplifies the process of iterating over the elements of a particular type of collection.
To illustrate, suppose a class wants to support iteration using the foreach loop construct of the C# language. The class must implement the “enumerator pattern.” The programmer codes the following using a foreach loop construct:
List1 list1 = ...;foreach(object obj in list1)  { DoSomething(obj); }
Code Fragment 4
“List1” is a class for a collection of elements of type “object,” and DoSomething( ) is a routine for doing something to the current object being iterated over in the List1 collection. The C# compiler expands that foreach code into the following code that uses a while loop construct.
Enumerator e = list1.GetEnumerator( );while(e.MoveNext( )){  object obj = e.Current;  DoSomething(obj);}
Code Fragment 5
The List1 data structure on whose instance the iteration occurs must support the GetEnumerator function (as well as the MoveNext method and Current property, described below) in order for the foreach loop to work. The creator of the List1 data structure implements the GetEnumerator function, which returns a ListEnumerator object:
public class List1{  internal object[ ] elements;   internal int count;   public ListEnumerator GetEnumerator( )     { return new ListEnumerator(this); }}
Code Fragment 6
The ListEnumerator object also implements the Current property (which indicates the current object in the List1) and the MoveNext method (for moving to the next object in the List1, if there is one.). The object maintains its internal state to allow moving to the next item each time around the loop. This internal state machine may be simple for the List1 data structure, but for data structures that require recursive traversal, such as binary trees, the state machine can be quite complicated.
Because implementing this enumerator pattern can require a great deal of effort and code on the developer's part, C# includes support that makes it easier for a class to dictate how the foreach loop will iterate over its contents. An iterator is the logical counterpart of the foreach loop construct. In C#, iterators are methods that incrementally compute and yield a sequence of values. Iterators make it easy for a type to specify how the foreach statement will iterate over its elements. An iterator is defined using the GetEnumerator function, returning an IEnumerator<T>. (In previous draft versions of the C# specification an iterator was defined similarly to a function in class implementation code, but using the foreach keyword, followed by an open and closed parenthesis pair.) For example, in the code fragment below, an iterator is declared for the List2 type. Notably, the return type of the iterator is determined by the user, and since the List2 class stores an “object” type internally, the return type of the iterator example below will be an IEnumerator<object>:
public class List2: IEnumerable<object>{  internal object[ ] elements;   internal int count;   public IEnumerator<object> GetEnumerator( ) { }}
Code Fragment 7
Iterators have or imply built-in state machines. When implementing the enumerator pattern, an internal state machine keeps track of the iterator's position in the data structure. The yield return keyword returns values back to the foreach statement that called the iterator. (In previous versions of the C# specification, the keyword “yield” was simply used; a “yield return statement” is sometimes more generally referred to herein as a “yield statement.”) The next time the foreach statement loops and calls the iterator again, the iterator will begin its execution where the previous yield statement left off. In the simple example below, three string types are yielded.
public class List3: IEnumerable<string>{  internal string[ ] elements;   internal int count;   public IEnumerator<string> GetEnumerator( )   {  yield return “Microsoft ”;     yield return “Corporation ”;     yield return “Research”;     yield return “Web Data”;   }}
Code Fragment 8
In the preceding code defining an implementation of List3, the GetEnumerator function indicates the iterator for the List3 type. The foreach loop (ultimately converted to a while loop calling the MoveNext method of the Enumerator object for list3) that calls this iterator will execute four times, each time receiving a string in the order specified by the four yield statements in the List3 type code, e.g., the following foreach( ) construct outputs “Microsoft Corporation Research Web Data” on the console.
List3 list3 = new List3( );foreach(string s in list3)  { Console.Write(s); }Console.Writeline( );
Code Fragment 9
To return to the earlier List2 example, to implement an iterator to traverse the elements in a List2 of “objects”, the iterator may be modified to step across the array of elements, yielding each item in the array in every iteration:
public class List2:IEnumerable<object>{  internal object[ ] elements;   internal int count;   public IEnumerator<object> GetEnumerator( )   {  foreach(object o in elements)       { yield return o; }   }}
Code Fragment 10
Iterators in C# handle the potentially messy chore of implementing the enumerator pattern in classes that implement the IEnumerable and IEnumerator interfaces. Rather than the programmer having to create the classes and build the state machine, the C# compiler will translate the “iterator” code into the appropriate classes and code that uses the enumerator pattern. In so doing, iterators provide a significant increase in developer productivity.
Iterators are also very useful in situations where the amount of data is not easily known at the start of the process, or where the data is coming from an outside, possibly asynchronous source. In this situation again, the use of an iterator can simplify programming, as the bulk of the complex logic for accessing the data is in the iterator.
Iterators in C# are examples of more general software constructs called “generators.” A generator is a construct that generates a stream of elements, where a “stream” is a variable-length sequence of elements. The elements can be base types such as integers or characters, or more complex types. In the examples given above, the foreach construct loops result in streams of elements being generated.
IV. Quadratic Effect in Nested Streams
The term “nested stream” describes a stream within another stream. For example, if a function that returns a stream repeatedly calls itself, the result of that recursive function (in a logical sense) will be streams of data within other streams. The problem with nested streams is that typically the streams have to be simplified or “flattened” into one stream before the data can be returned to the original caller. One reason for flattening may be simplification of results in the nested stream. Another reason may be type consistency—where data has to be flattened along the way because incompatible types may result otherwise (e.g., if a function is of a type “stream of integers,” recursive calls to that function will return “a stream of a stream of integers,” etc., a type that is incompatible with the original type “stream of integer”). So before the data can be returned and resolved, the streams need to be flattened. As with other recursive functions, the deeper and more complex the nesting of streams becomes, the poorer the performance.
The examples of iterators given above were not recursive. Iterators are typically associated with non-recursive functions because iterators perform poorly on recursive functions. Consider the following pseudocode example for the function FromTo.
int* FromTo(int n, int m){if(n<= m) {yield n;foreach(int i in FromTo(n + 1, m)) {yield i; }}}
Code Fragment 11
In this code fragment, int* means “stream of integers.” The function FromTo returns a stream of integers to a caller. (Note that the type of the FromTo function is int*, which allows the function itself to be used as the collection iterated across in the foreach loop.) Other languages use other symbols or conventions to indicate a stream return type or other collection of elements. (For example, C# uses the term IEnumerable<int> to indicate a stream of integers as an object implementing the IEnumerable interface. And, in C#, the C# compiler would attempt to convert corresponding FromTo code into code for a class implementing IEnumerable/IEnumerator interfaces, as mentioned above.)
Suppose the function FromTo is initially called as follows.
foreach(int j in FromTo(0,10){Console.WriteLine(j); }
Code Fragment 12
The function FromTo is called to determine the collection to be iterated over in the foreach loop. (In C#, this foreach code would be converted by the C# compiler into a while loop calling a MoveNext method of a newly instantiated enumerator object for the collection, as discussed above with respect to Code fragments 4 and 5). FromTo is passed the values 0 and 10 for n and m, respectively, and FromTo(0,10) returns a stream of 11 integers (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10). The foreach loop iterates through the returned stream of integers and outputs each integer in the stream.
Stepping into and through the FromTo function of code fragment 11 illustrates the recursive process. Within FromTo, an initial comparison determines if n is less than or equal to m. To start, n (0) is less than m (10), which means that the computer executes the “yield n” statement. The yield statement produces the value “0.” FIG. 1 shows the values produced by the yield statements through the entire call to FromTo(0,10). The value 0 at the left of the top row is the value produced by “yield n” in the n=0 level.
FromTo continues execution. The next statement to be executed is the foreach statement, which recursively calls FromTo(n+1,m). At the next level, n is 1, and FromTo yields a 1 value and then recursively calls FromTo(n+1, m). Thus, at each level, the function FromTo yields the value n (shown as the far left of the respective rows in FIG. 1), then recursively goes to the next level. This continues until FromTo(11,10) is called, at which point the comparison (n<=m) is false and FromTo returns an empty stream of integers to the previous recursive caller (at level n=10). The foreach loop at that level exits (having nothing to iterate over in the returned empty set) and FromTo returns a stream of one integer (10) to the recursive caller (at level n=9). It is at this point that the real problem of the quadratic effect is manifest. Each recursive level yields not only the current value of n, but all higher values of n as well (through the loop of yield return i statements). So, the foreach loop in FromTo at the level where n=9 still has one element (i.e., 10) to iterate over, which means the yield return i statement is executed for i=10 (shown as the far right of the second row from the bottom).
FIG. 1 shows another representation of the total number of yields required to output the stream (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10). Another way of representing this data is to show the nested streams: (0, (1, (2, (3, (4, (5, (6, (7, (8, (9, (10, ( ))))))))))).
Returning to the process, the foreach loop continues executing the yield i statement for values returned from the lower level, until the FromTo loop returns from the level n=0 with the stream (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10), which is iterated over by the caller in code fragment 12 and output by the Console.WriteLine statement. The yields at the level where n=0 are shown in the top row of FIG. 1. The remaining yields are side effects of the recursion, and can affect performance significantly.
The evaluation of FromTo(0,10) results in an explicit flattening of the nested streams of integers into a single, simple stream. In the course of processing, however, the recursive calls of FromTo result in an inefficient number of yield operations. Even though the goal of FromTo was to return a stream of x integers (here, x=11), the processing resulted in
      x    ⁡          (              x        +        1            )        2yields (here, 66). This is an example of a quadratic relation, where the complexity of processing x elements can be characterized as O(x2). The disparity between linear and quadratic complexity becomes more pronounced for higher values of x, for example, for x=1000 integers, processing would result in more than half a million yields.
A similar situation happens in languages with simple generators such as Python or C# when programmers manually flatten the results of recursive generators. For example, the following C# method will execute a quadratic number of yields due to the repeated explicit flattening of the recursively generated streams.
IEnumerable<int> Down(int n) {if(n>0){foreach(int i in Down(n−1)) {yield return i;}}yield return n;}
Code Fragment 13
In many document oriented languages, such as XQuery, XPath, XDuce, XTatic, CDuce, and X#, the notion of automatically flattening nested streams and removal of embedded empty streams is supported. For example, in XQuery the sequence (((((( ),1),2),3),4),5) is naively flattened into the single sequence (1, 2, 3, 4, 5), where ( ) is an empty stream. Essentially, the sequence (((((( ),1),2),3),4),5) is the sequence ((((( ),1),2),3),4) (which in turn must be flattened) and 5. Even in these languages, the naive flattening of nested streams can result in quadratic time complexity due to repeated implicit flattening of inner streams.
As a result of these limitations, sequences in XQuery, streams in X#, and iterators in C# and Python, to name a few generators, are limited to simple, non-recursive generators for effective usage. Iterators in C#, however, are a very useful construct for which effective operation in conjunction with recursion would be advantageous. XQuery and XPath are important languages for the World Wide Web which contain many implicitly recursive path queries (descendant queries) whose performance is sub-optimal if naive flattening strategies are used. In particular, there is a need in these and other contexts for a mechanism to flatten nested streams quickly and effectively.